/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/longest-palindromic-substring
@Language: C++
@Datetime: 16-02-09 05:57
*/

class Solution {
public:
    /**
     * @param s input string
     * @return the longest palindromic substring
     */
    string longestPalindrome(string& s) {
        // Write your code here
        vector<char> temp;
        vector<int> DP;
        temp.push_back('@');
        DP.push_back(0);
        for(int i=0;i<s.length();++i){
            temp.push_back('#');
            temp.push_back(s[i]);
            DP.push_back(0);
            DP.push_back(0);
        }
        temp.push_back('#');
        temp.push_back('\0');
        DP.push_back(0);
        DP.push_back(0);
        
        int len=1,id=0,maxid=0;
        for(int i=0;i<temp.size()-1;++i){
            if (maxid > i) DP[i] = (DP[id*2-i]<maxid-i?DP[id*2-i]:maxid-i);
            else DP[i]=1;
            while(i-DP[i]>=0 && temp[i+DP[i]] == temp[i-DP[i]]) ++DP[i];
            if (DP[i]+i > maxid) maxid = DP[id=i]+i;
        }
        for(int i=DP.size()-1;i>=0;--i)
            if (DP[i]>len)
                len = DP[id=i];
            
        string ans;
        for(int i=id-len+1;i<id+len;++i)
            if (temp[i]!='#') ans.push_back(temp[i]);
        return ans;
    }
};